#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include "euler/digits.hpp"
#include "euler.h"

BEGIN_PROBLEM(303, solve_problem_303)
	PROBLEM_TITLE("Multiples with small digits")
	PROBLEM_ANSWER("1111981904675169")
	PROBLEM_DIFFICULTY(2)
	PROBLEM_FUN_LEVEL(2)
	PROBLEM_TIME_COMPLEXITY("n^2")
	PROBLEM_SPACE_COMPLEXITY("n")
	PROBLEM_KEYWORDS("digits")
END_PROBLEM()

static bool all_small_digits(int n)
{
	return std::all_of(euler::rdigits<10>(n).begin(), euler::rdigits<10>(n).end(),
		[](int d) -> bool { return d <= 2; }
	);
}

// Find the least multiple, m, of n, such that (n*m) only contains digits 0,1,2.
static long long find_least_multiple(int n)
{
	std::vector<long long> best(n, -1); // The least multiplier, m, such that
	// best[c] = m such that m * n yields carry c.

	// Breadth first search. The total search space is just n nodes.
	std::vector<int> nodes; // The carries to expand
	nodes.reserve(n);

	// Create the root node.
	nodes.push_back(0);
	best[0] = 0;

	// Expand one more level of nodes.
	bool found = false;
	long long power = 1;
	long long result = std::numeric_limits<long long>::max();
	for (int i = 0; !found; power *= 10)
	{
		int last = (int)nodes.size();
		for (; i < last; i++)
		{
			int c = nodes[i];
			for (int d = (i == 0)? 1 : 0; d <= 9; d++)
			{
				if ((n*d+c)%10 <= 2)
				{
					int c2 = (n*d+c)/10;
					long long tt = best[c] + d * power;
					bool expanded = (best[c2] >= 0);
					if (best[c2] < 0 || best[c2] > tt)
						best[c2] = tt;

					// Expand children if not yet done
					if (all_small_digits(c2))
					{
						result = std::min(result, tt);
						found = true;
					}
					if (!expanded)
					{
						nodes.push_back(c2);
					}
				}
			}
		}
	}
	return result;
}

static void solve_problem_303()
{
#if 0
	const int N = 100;
#else
	const int N = 10000;
#endif

	bool verbose = false;
	long long sum = 0;
	for (int n = 1; n <= N; n++)
	{
		long long m = find_least_multiple(n);
		if (verbose)
			std::cout << "Least multiple of " << n << " is " << (m * n) << std::endl;
		sum += m;
	}
	std::cout << sum << std::endl;
}
